package Tree.BST;

import Utils.Pair;
import Utils.TreeNode;

import java.lang.reflect.Array;
import java.util.*;

/**
 * 二叉搜索树中的众数
 * 给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
 *
 * 假定 BST 有如下定义：
 *
 * 结点左子树中所含结点的值小于等于当前结点的值
 * 结点右子树中所含结点的值大于等于当前结点的值
 * 左子树和右子树都是二叉搜索树
 * 例如：
 * 给定 BST [1,null,2,2],
 *
 *    1
 *     \
 *      2
 *     /
 *    2
 * 返回[2].
 *
 * 提示：如果众数超过1个，不需考虑输出顺序
 *
 * 进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-mode-in-binary-search-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class findMode {
    /**
     * 方法一：采用额外空间
     * @param root
     * @return
     */
    private Map<Integer, Integer> map = new HashMap<>();

    public int[] findMode(TreeNode root) {
        if (root == null) return new int[0];
        List<Integer> result = new ArrayList<>();
        inOrder(root);
        int maxValue = Collections.max(map.values());
        for (int key: map.keySet()) {
            if (map.get(key) == maxValue) {
                result.add(key);
            }
        }
        int[] res = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            res[i] = result.get(i);
        }
        return res;
    }

    private void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        map.put(root.val, map.getOrDefault(root.val, 0) + 1);
        inOrder(root.right);
    }

    /**
     * 方法二：二叉搜索树的中序遍历是一个递增的序列，因此可以维护两个值，
     * 一个curCnt用于保存当前数字出现的次数，一个maxCnt用于保存最大出现次数
     */
    private int curCnt = 1;
    private int maxCnt = 1;
    private TreeNode preNode = null;

    public int[] findModeI(TreeNode root) {
        if (root == null) return new int[0];
        List<Integer> result = new ArrayList<>();
        inOrderI(root, result);
        int[] res = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            res[i] = result.get(i);
        }
        return res;
    }

    private void inOrderI(TreeNode node, List<Integer> nums) {
        if (node == null) return;
        inOrderI(node.left, nums);
        if (preNode != null) {
            if (node.val == preNode.val) curCnt++;
            else curCnt = 1;
        }
        if (curCnt > maxCnt) {
            maxCnt = curCnt;
            nums.clear();
            nums.add(node.val);
        } else if (curCnt == maxCnt) {
            nums.add(node.val);
        }
        preNode = node;
        inOrderI(node.right, nums);
    }
}
